package Demo2;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Test2 {

    public static void main(String[] args) {
        /*
         1. 已知带头结点的动态单链表 L 中的结点是按整数值递增排序的，试写一算法将值为 x
        的结点插入到表 L 中，使 L 仍然有序。要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。
        */
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.insert(2);
        singleLinkedList.insert(4);
        singleLinkedList.insert(5);
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入要插入的数");
//        输入三个数 代表着三种情况
        int n1 = scanner.nextInt();
        singleLinkedList.insert(n1);
        singleLinkedList.printList();

        int n2 = scanner.nextInt();
        singleLinkedList.insert(n2);
        singleLinkedList.printList();

        int n3 = scanner.nextInt();
        singleLinkedList.insert(n3);
        singleLinkedList.printList();

//        反转链表
//
        singleLinkedList.reverse();
        System.out.println("链表反转: ");
        singleLinkedList.printList();


//             假设有两个按元素值递增有序的线性表 A 和 B，均以单链表作存储结构，试编写算法
//              将 A 表和 B 表归并成一个按元素值递减有序的线性表性表 C，并要求利用原表的空间存放 C
        SingleLinkedList listA = new SingleLinkedList();
        SingleLinkedList listB = new SingleLinkedList();
        System.out.println("合并逆序: ");

        // 向链表A中插入数据，保持有序
        listA.insert(1);
        listA.insert(3);
        listA.insert(5);
        listA.insert(7);

        // 向链表B中插入数据，保持有序
        listB.insert(2);
        listB.insert(4);
        listB.insert(6);
        listB.insert(8);
        SingleLinkedList listC = singleLinkedList.mergeDescending(listA,listB);
        listC.printList();
    }
}
